﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.OnlyQuantityModeling
{
    public class SpaceSavingDynamicCoinChanger : IDynamicCoinChanger
    {
        protected readonly IList<int> _values;
        protected readonly int _n;
        protected readonly IList<double> _weights;
        protected readonly int _maxmem;

        public SpaceSavingDynamicCoinChanger(IList<int> values, IList<double> weights = null)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0, _n).ToAlgoritmiaList();
            _maxmem = _values.Max();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            var memLength = Math.Max(_maxmem, Q);
            var mem = new double[memLength];
            mem[0] = 0;
            for(int q = 1; q <= Q;q++)
            {
                mem[q%memLength] =
                    Enumerable.Range(0, _n).Where(i => _values[i] <= q).Select(
                        i => mem[(q - _values[i])%memLength] + _weights[i]).DefaultIfEmpty(double.PositiveInfinity).Min();
            }
            return mem[Q%memLength];
        }

        #endregion
    }
}
